package com.qfedu.entity.course10;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class GraphTraverse {
    private String[] vertexes = {"A", "B", "C", "D", "E", "F"};
    private int[][] edges = {
            {0, 1, 1, 1, 1, 1},
            {1, 0, 0, 1, 1, 1},
            {1, 0, 0, 1, 1, 1},
            {1, 1, 1, 0, 1, 1},
            {1, 1, 1, 1, 0, 0},
            {1, 1, 1, 1, 0, 0}
    };
    private int number = vertexes.length;
    //标记第i个顶点是否访问过
    private boolean[] flags = new boolean[number];

    private void dfs() {
        flags = new boolean[number];
        for (int i = 0; i < number; i++) {
            if (!flags[i]) {// 当前顶点没有被访问
                dfs(i);
            }
        }
        System.out.println();
    }

    private void dfs(int i) {
        flags[i] = true;
        System.out.print("访问 " + vertexes[i] + "\t");
        for (int j = 0; j < number; j++) {
            if (!flags[j] && edges[i][j] != 0) {
                dfs(j);
            }
        }
    }

    private void dfsNoRecursion() {
        flags = new boolean[number];
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < number; i++) {
            if (!flags[i]) {
                flags[i] = true;
                System.out.print("访问 " + vertexes[i] + "\t");
                stack.push(i);
            }
            while (!stack.isEmpty()) {
                int k = stack.pop();
                for (int j = 0; j < number; j++) {
                    if (edges[k][j] == 1 && !flags[j]) {
                        flags[j] = true;
                        System.out.print("访问 " + vertexes[j] + "\t");
                        stack.push(j);
                        break;
                    }
                }

            }
        }
        System.out.println();
    }

    private void bfs() {
        flags = new boolean[number];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < number; i++) {
            if (!flags[i]) {
                flags[i] = true;
                System.out.print("访问 " + vertexes[i] + "\t");
                queue.add(i);
                while (!queue.isEmpty()) {
                    int k = queue.poll();
                    for (int j = 0; j < number; j++) {
                        if (edges[k][j] != 0 && !flags[j]) {
                            flags[j] = true;
                            System.out.print("访问 " + vertexes[j] + "\t");
                            queue.add(j);
                        }
                    }
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        GraphTraverse graphTraverse = new GraphTraverse();
        System.out.println("dfs:");
        graphTraverse.dfs();
        System.out.println("dfsNoRecursion:");
        graphTraverse.dfsNoRecursion();
        System.out.println("bfs:");
        graphTraverse.bfs();
    }
}
